/**
 * 串联所有单词子串
 *
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 *  s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 *
 * 示例 1：
 * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
 * 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
 * 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
 * 输出顺序无关紧要。返回 [9,0] 也是可以的。
 *
 * 示例 2：
 * 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
 * 输出：[]
 * 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
 * s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
 * 所以我们返回一个空数组。
 *
 * 示例 3：
 * 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 * 输出：[6,9,12]
 * 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
 * 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
 * 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
 * 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
 *
 * 提示：
 * 1 <= s.length <= 104
 * 1 <= words.length <= 5000
 * 1 <= words[i].length <= 30
 * words[i] 和 s 由小写英文字母组成
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 寻找字符串中包含的字符数组, 因为这字符数组没有顺序要求, 所以我们可以先将字符数组中的字符全存在
 * HashMap中, 因为我们寻找的是有这些字符组成的字符串, 所以我们在遍历的时候还可以定义一个hashMap
 * 来和之前的 HashMap进行比较, 若是字符数都达到了要求, 就是成功组成了字符串
 * 时间复杂度 : O(len)
 * 空间复杂度 : O(len)
 */

public class Main {
    public List<Integer> findSubstring(String s, String[] words) {

        // 定义各一个list表, 来记录返回结果
        List<Integer> list = new ArrayList<>();

        // len : 字符串个数, n : 字符串长度
        int len = words.length, n = words[0].length();

        // 第一个 HashMap 用来记录 words 中字符串的个数
        Map<String, Integer> map = new HashMap<>();

        // 将字符串全都加入 map 中
        for (int i = 0; i < len; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        // 这里我们循环遍历 n 次
        // 因为我们是以字符串的长度 n 来遍历的, 所以当我走过第一个 n 后, 就开始重新遍历第一次遍历的后面的结果了
        // 越往后面还是都已经遍历过, 所以我们只需要遍历前面 n 个就行
        // 这个 n 指的是 字符串数组中字符串的长度
        for (int i = 0; i < n; i++) {

            // 定义一个 HashMap 变量用来和map进行比较
            Map<String, Integer> hash = new HashMap<>();

            // right : 进入字符串的开始位
            // left : 出字符串的开始位
            // 首先right 不能超过 s 长度, 其次, 我们求字符串的时候因为是向后面求的, 所以我们要保证数组不会越界需要减去字符串的长度
            // 因为后面用到了substring, 右开, 所以要取等
            // right 每次循环结束后都需要 += n
            // k : 用来记录在 right 和 left 的区间内有多少个符合要求的字符出现, 要是与 words 的长度相等, 就说明已经满足要求
            for (int left = i, right = i, k = 0; right <= s.length() - n; right += n) {

                // in为入字符串
                String in = s.substring(right, right + n);

                // 二话不说, 先将 in 加入 hash, 后面解释
                hash.put(in, hash.getOrDefault(in, 0) + 1);

                // 与map中数据进行比较
                // 这里我们要注意, 因为我们在比较字符串的数量的时候, hash中这种字符的数量可能已经满足需要,
                // 此时我们需要改变 k 的值吗, 需要在 hash中为这个字符串的数量在加一吗?
                // 如果我们不加在 hash 中的这个字符串数量加一, 当我们在后续出字符串的时候, 如果将前面这个字符串出出去之后,
                // 那我们之前在遇到这个字符的时候又没有将他加入进去, 这就会造成了这种字符串的损失....
                // 所以我们要将这种字符加入 hash, 这就是为什么我一开始不管啥就将这个字符串加入 hash 中的理由
                // 那我们们对 k 怎么处理呢, 首先我们肯定是不能加的, 因为如果加了, 就会顶替另一种字符串, 这明显不是我们想要的
                // 所以我们在之前加入了 hash, 我们要想一种比较方式解决这种提前加入的方式
                // 引入 <= 和 map比较, 这样之前加入就会大于, 就不会改变 k 的值了
                // = 是因为我们提前将这个字符串加入的, 所以我们需要带 = 玩一个
                if (hash.get(in) <= map.getOrDefault(in, 0)) {
                    k++;
                }

                // 在出字符串之前我们需要先带 k 玩一下, 要是已经满足要求就将这个 left加入返回列表
                if (k == len) {
                    list.add(left);
                }

                // 要是区间已经满足条件了, 我们就需要出 字符串了
                // 因为我们是提前用到后面的数组, 所以right的位置并不是我们想象的正好与 left隔了 len * n的距离, 而是差了一个 n
                if (right - left == len * n - n) {

                    // out : 除字符串
                    String out = s.substring(left, left + n);

                    // 因为前面加入的原因, 所以我们这里也要当个 out的数量小于等于 map中 out 的数量数才开始改变 k 的值,
                    // 因为在 out 大于 map中 out 的时候说明上次遇到 k 的时候虽然没有改变 k 的值, 但我记录下来了,
                    // 就相当于有了一层复活甲, 在这里复活了, 所以我们不改变 k 的值
                    if (hash.get(out) <= map.getOrDefault(out, 0)) {
                        k--;
                    }

                    // 不管是否要 改变 k 的值
                    // 是一定要出字符串的
                    hash.put(out, hash.get(out) - 1);

                    // left 也是字符串遍历的, 所以要跳字符串
                    left += n;
                }
            }
        }
        // 返回结果
        return list;
    }

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        System.out.println(test.findSubstring("aaa", new String[]{"a", "a"}));
    }
}